/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/course-schedule
   @Language: C++
   @Datetime: 20-01-07 11:58
   */

// Method 1, DFS.
class Solution {
	bool hasCircle(vector<list<int> > &deps, int course, vector<int> &courses){
		if(courses[course]==0) return false;
		if(courses[course]==-1) return true;
		courses[course]=-1;
		for(const auto &dep:deps[course])
			if(hasCircle(deps, dep, courses)) return true;
		courses[course]=0;
		return false;
	}
public:
	bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
		vector<list<int> > deps(numCourses, list<int>());
		vector<int> courses(numCourses, 0);
		for(const auto &v:prerequisites){
			deps[v[0]].push_back(v[1]);
			courses[v[0]]=1;
		}
		for(int course=0; course<numCourses; ++course)
			if(hasCircle(deps, course, courses)) return false;
		return true;
	}
};

// Method 2, Topological Sort. 
class Solution {
public:
	bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
		vector<list<int> > edges(numCourses, list<int>());
		vector<int> indegrees(numCourses, 0);
		for(const auto &v:prerequisites){
			edges[v[1]].push_back(v[0]);
			++indegrees[v[0]];
		}
		queue<int> courses;
		for(int i=0; i<numCourses; ++i)
			if(indegrees[i]==0) courses.push(i);
		for(; !courses.empty(); --numCourses, courses.pop())
			for(const auto &node:edges[courses.front()])
				if(--indegrees[node]==0) courses.push(node);
		return numCourses==0;
	}
};
